Product Code Database
Example Keywords: light -ps3 $87-101
barcode-scavenger
   » » Wiki: Boolean Algebra (structure)
Tag Wiki 'Boolean Algebra (structure)'.
Tag

Boolean algebra (structure)
Search for boolean algebra
 ( ) 

 C O N T E N T S 
Rank: 100%
Bluestar Bluestar Bluestar Bluestar Blackstar
  1. Wiki
  2. Comments
  3. Media

In , a Boolean algebra or Boolean lattice is a complemented distributive lattice. This type of algebraic structure captures essential properties of both set operations and operations. A Boolean algebra can be seen as a generalization of a algebra or a field of sets, or its elements can be viewed as generalized . It is also a special case of a De Morgan algebra and a Kleene algebra (with involution).

Every Boolean algebra gives rise to a , and vice versa, with ring multiplication corresponding to conjunction or meet ∧, and ring addition to or symmetric difference (not disjunction ∨). However, the theory of Boolean rings has an inherent asymmetry between the two operators, while the and theorems of Boolean algebra express the symmetry of the theory described by the duality principle.

History
The term "Boolean algebra" honors (1815–1864), a self-educated English mathematician. He introduced the initially in a small pamphlet, The Mathematical Analysis of Logic, published in 1847 in response to an ongoing public controversy between Augustus De Morgan and William Hamilton, and later as a more substantial book, The Laws of Thought, published in 1854. Boole's formulation differs from that described above in some important respects. For example, conjunction and disjunction in Boole were not a dual pair of operations. Boolean algebra emerged in the 1860s, in papers written by and Charles Sanders Peirce. The first systematic presentation of Boolean algebra and distributive lattices is owed to the 1890 Vorlesungen of Ernst Schröder. The first extensive treatment of Boolean algebra in English is A. N. Whitehead's 1898 Universal Algebra. Boolean algebra as an axiomatic algebraic structure in the modern axiomatic sense begins with a 1904 paper by Edward V. Huntington. Boolean algebra came of age as serious mathematics with the work of in the 1930s, and with 's 1940 Lattice Theory. In the 1960s, Paul Cohen, , and others found deep new results in mathematical logic and axiomatic set theory using offshoots of Boolean algebra, namely forcing and Boolean-valued models.

Definition
A Boolean algebra is a set , equipped with two (called "meet" or "and"), (called "join" or "or"), a (called "complement" or "not") and two elements and in (called "bottom" and "top", or "least" and "greatest" element, also denoted by the symbols and , respectively), such that for all elements , and of , the following hold:

: >
complements
Note, however, that the absorption law and even the associativity law can be excluded from the set of axioms as they can be derived from the other axioms (see Proven properties).

A Boolean algebra with only one element is called a trivial Boolean algebra or a degenerate Boolean algebra. (In older works, some authors required and to be distinct elements in order to exclude this case.)

It follows from the last three pairs of axioms above (identity, distributivity and complements), or from the absorption axiom, that

    if and only if     .
The relation defined by if these equivalent conditions hold, is a with least element 0 and greatest element 1. The meet and the join of two elements coincide with their and , respectively, with respect to ≤.

The first four pairs of axioms constitute a definition of a .

It follows from the first five pairs of axioms that any complement is unique.

The set of axioms is self-dual in the sense that if one exchanges with and with in an axiom, the result is again an axiom. Therefore, by applying this operation to a Boolean algebra (or Boolean lattice), one obtains another Boolean algebra with the same elements; it is called its dual.

Examples
  • The simplest non-trivial Boolean algebra, the two-element Boolean algebra, has only two elements, and , and is defined by the rules:
{ class="wikitable"
| | width="30" | |
| | width="40" | |
|}

* It has applications in , interpreting as false, as true, as and, as or, and as not. Expressions involving variables and the Boolean operations represent statement forms, and two such expressions can be shown to be equal using the above axioms if and only if the corresponding statement forms are logically equivalent.

* The two-element Boolean algebra is also used for circuit design in electrical engineering; here 0 and 1 represent the two different states of one in a , typically high and low . Circuits are described by expressions containing variables, and two such expressions are equal for all values of the variables if and only if the corresponding circuits have the same input–output behavior. Furthermore, every possible input–output behavior can be modeled by a suitable Boolean expression.

* The two-element Boolean algebra is also important in the general theory of Boolean algebras, because an equation involving several variables is generally true in all Boolean algebras if and only if it is true in the two-element Boolean algebra (which can be checked by a trivial brute force algorithm for small numbers of variables). This can for example be used to show that the following laws ( Consensus theorems) are generally valid in all Boolean algebras:
**
**

  • The (set of all subsets) of any given nonempty set forms a Boolean algebra, an algebra of sets, with the two operations (union) and (intersection). The smallest element 0 is the and the largest element is the set itself.

* After the two-element Boolean algebra, the simplest Boolean algebra is that defined by the of two atoms:
{ class="wikitable"
| | width="30" | |
| | width="40" | |
|}

  • The set of all subsets of that are either finite or is a Boolean algebra and an algebra of sets called the finite–cofinite algebra. If is infinite then the set of all cofinite subsets of , which is called the Fréchet filter, is a free on . However, the Fréchet filter is not an ultrafilter on the power set of .
  • Starting with the propositional calculus with sentence symbols, form the Lindenbaum algebra (that is, the set of sentences in the propositional calculus modulo logical equivalence). This construction yields a Boolean algebra. It is in fact the free Boolean algebra on generators. A truth assignment in propositional calculus is then a Boolean algebra homomorphism from this algebra to the two-element Boolean algebra.
  • Given any set with a least element, the interval algebra is the smallest Boolean algebra of subsets of containing all of the half-open intervals such that is in and is either in or equal to . Interval algebras are useful in the study of Lindenbaum–Tarski algebras; every Boolean algebra is isomorphic to an interval algebra.

  • For any , the set of all positive of , defining if , forms a distributive lattice. This lattice is a Boolean algebra if and only if is square-free. The bottom and the top elements of this Boolean algebra are the natural numbers and , respectively. The complement of is given by . The meet and the join of and are given by the greatest common divisor () and the least common multiple () of and , respectively. The ring addition is given by . The picture shows an example for . As a counter-example, considering the non-square-free , the greatest common divisor of 30 and its complement 2 would be 2, while it should be the bottom element 1.
  • Other examples of Boolean algebras arise from : if is a topological space, then the collection of all subsets of that are forms a Boolean algebra with the operations (union) and (intersection).
  • If is an arbitrary ring then its set of central idempotents, which is the set
A = \left\{e \in R : e^2 = e \text{ and } ex = xe \; \text{ for all } \; x \in R\right\}, becomes a Boolean algebra when its operations are defined by and .

Homomorphisms and isomorphisms
A between two Boolean algebras and is a function such that for all , in :
,
,
,
.

It then follows that for all in . The class of all Boolean algebras, together with this notion of morphism, forms a of the of lattices.

An isomorphism between two Boolean algebras and is a homomorphism with an inverse homomorphism, that is, a homomorphism such that the composition is the identity function on , and the composition is the identity function on . A homomorphism of Boolean algebras is an isomorphism if and only if it is .

Boolean rings
Every Boolean algebra gives rise to a ring by defining (this operation is called symmetric difference in the case of sets and XOR in the case of logic) and . The zero element of this ring coincides with the 0 of the Boolean algebra; the multiplicative identity element of the ring is the of the Boolean algebra. This ring has the property that for all in ; rings with this property are called .

Conversely, if a Boolean ring is given, we can turn it into a Boolean algebra by defining and . Since these two constructions are inverses of each other, we can say that every Boolean ring arises from a Boolean algebra, and vice versa. Furthermore, a map is a homomorphism of Boolean algebras if and only if it is a homomorphism of Boolean rings. The of Boolean rings and Boolean algebras are equivalent; in fact the categories are isomorphic.

Hsiang (1985) gave a rule-based algorithm to check whether two arbitrary expressions denote the same value in every Boolean ring.

More generally, Boudet, Jouannaud, and Schmidt-Schauß (1989) gave an algorithm to solve equations between arbitrary Boolean-ring expressions. Employing the similarity of Boolean rings and Boolean algebras, both algorithms have applications in automated theorem proving.

Ideals and filters
An ideal of the Boolean algebra is a nonempty subset such that for all , in we have in and for all in we have in . This notion of ideal coincides with the notion of in the Boolean ring . An ideal of is called prime if and if in always implies in or in . Furthermore, for every we have that , and then if is prime we have or for every . An ideal of is called maximal if and if the only ideal properly containing is itself. For an ideal , if and , then or is contained in another proper ideal . Hence, such an is not maximal, and therefore the notions of prime ideal and maximal ideal are equivalent in Boolean algebras. Moreover, these notions coincide with ring theoretic ones of and in the Boolean ring .

The dual of an ideal is a filter. A filter of the Boolean algebra is a nonempty subset such that for all , in we have in and for all in we have in . The dual of a maximal (or prime) ideal in a Boolean algebra is . Ultrafilters can alternatively be described as 2-valued morphisms from to the two-element Boolean algebra. The statement every filter in a Boolean algebra can be extended to an ultrafilter is called the ultrafilter lemma and cannot be proven in Zermelo–Fraenkel set theory (ZF), if ZF is . Within ZF, the ultrafilter lemma is strictly weaker than the axiom of choice. The ultrafilter lemma has many equivalent formulations: every Boolean algebra has an ultrafilter, every ideal in a Boolean algebra can be extended to a prime ideal, etc.

Representations
It can be shown that every finite Boolean algebra is isomorphic to the Boolean algebra of all subsets of a finite set. Therefore, the number of elements of every finite Boolean algebra is a power of two.

Stone's celebrated representation theorem for Boolean algebras states that every Boolean algebra is isomorphic to the Boolean algebra of all in some ( totally disconnected ) topological space.

Axiomatics
{ align="left" class="collapsible collapsed" style="text-align:left" ! UId1 !! !! colspan="2" If x ∨ o = x for all x, then o = 0
If x ∨ o = x, then
0
by assumption
by Cmm1
by Idn1
| UId2   dual   If x ∧ i = x for all x, then i = 1 |- valign="top" |
x ∨ x
by Idn2
by Cpl1
by Dst1
by Cpl2
by Idn1
| Idm2   dual   x ∧ x = x |- valign="top" |
x ∨ 1
by Idn2
by Cmm2
by Cpl1
by Dst1
by Idn2
by Cpl1
| Bnd2   dual   x ∧ 0 = 0 |- valign="top" |
x ∨ ( x ∧ y)
by Idn2
by Dst2
by Cmm1
by Bnd1
by Idn2
| Abs2   dual   x ∧ ( x ∨ y) = x |- valign="top" | colspan="2" |
If x ∨ xn = 1 and x ∧ xn = 0, then
xn
by Idn2
by Cpl1
by Dst2
by Cmm2
by assumption
by Cpl2
by Cmm2
by Dst2
by assumption
by Idn2
|- valign="top" | colspan="2" |
by Cmm1, Cpl1
by Cmm2, Cpl2
by UNg
|- valign="top" |
x ∨ (¬ x ∨ y)
by Idn2
by Cmm2
by Cpl1
by Dst1
by Abs2
by Cpl1
| A2   dual   x ∧ (¬ x ∧ y) = 0 |- valign="top" |
( x ∨ y) ∨ (¬ x ∧ ¬ y)
by Dst1
by Cmm1
by DNg
by A1
by Idn2
| B2   dual   ( x ∧ y) ∧ (¬ x ∨ ¬ y) = 0 |- valign="top" |
( x ∨ y) ∧ (¬ x ∧ ¬ y)
by Cmm2
by Dst2
by Cmm2
by A2
by Idn1
| C2   dual   ( x ∧ y) ∨ (¬ x ∨ ¬ y) = 1 |- valign="top" |
by B1, C1, and UNg
| DMg2   dual   ¬( x ∧ y) = ¬ x ∨ ¬ y |- valign="top" |
( x ∨ ( y ∨ z)) ∨ ¬ x
by Cmm1
by DNg
by A1
| D2   dual   ( x∧( y∧ z)) ∧ ¬ x = 0 |- valign="top" |
y ∧ ( x ∨ ( y ∨ z))
by Dst2
by Abs2
by Cmm1
by Abs1
| E2   dual   y ∨ ( x∧( y∧ z)) = y |- valign="top" |
( x ∨ ( y ∨ z)) ∨ ¬ y
by Cmm1
by Idn2
by Cmm2
by Cpl1
by Cmm1
by Dst1
by E1
by Cmm1
by Cpl1
| F2   dual   ( x∧( y∧ z)) ∧ ¬ y = 0 |- valign="top" |
( x ∨ ( y ∨ z)) ∨ ¬ z
by Cmm1
by F1
| G2   dual   ( x∧( y∧ z)) ∧ ¬ z = 0 |- valign="top" |
¬(( x ∨ y) ∨ z) ∧ x
by DMg1
by DMg1
by Cmm2
by Idn1
by Cmm1
by Cpl2
by Dst2
by Cmm2
by E2
by Cpl2
| H2   dual   ¬(( x∧ y)∧ z) ∨ x = 1 |- valign="top" |
¬(( x ∨ y) ∨ z) ∧ y
by Cmm1
by H1
| I2   dual   ¬(( x∧ y)∧ z) ∨ y = 1 |- valign="top" |
¬(( x ∨ y) ∨ z) ∧ z
by DMg1
by Cmm2
by Cmm2
by A2
| J2   dual   ¬(( x∧ y)∧ z) ∨ z = 1 |- valign="top" |
( x∨( y∨ z)) ∨ ¬(( x ∨ y) ∨ z)
by DMg1
by DMg1
by Dst1
by Dst1
by D1, F1, G1
by Idn2
| K2   dual   ( x ∧ ( y ∧ z)) ∧ ¬(( x ∧ y) ∧ z) = 0 |- valign="top" |
( x ∨ ( y ∨ z)) ∧ ¬(( x ∨ y) ∨ z)
by Cmm2
by Dst2
by Dst2
by H1, I1, J1
by Idn1
| L2   dual   ( x ∧ ( y ∧ z)) ∨ ¬(( x ∧ y) ∧ z) = 1 |- valign="top" |
by K1, L1, UNg, DNg
| Ass2   dual   x ∧ ( y ∧ z) = ( x ∧ y) ∧ z |- | colspan="2" |
Unique Identity
Unique Negation
De Morgan's Law
|}
x ∨ 0 = xx ∧ 1 = x
x ∨ y = y ∨ xx ∧ y = y ∧ x
x ∨ ( y∧ z) = ( x∨ y) ∧ ( x∨ z)x ∧ ( y∨ z) = ( x∧ y) ∨ ( x∧ z)
x ∨ ¬ x = 1x ∧ ¬ x = 0
{ align="left" class="collapsible" style="text-align:left"
Complements
|}

The first axiomatization of Boolean lattices/algebras in general was given by the English philosopher and mathematician Alfred North Whitehead in 1898. It included the above axioms and additionally and . In 1904, the American mathematician Edward V. Huntington (1874–1952) gave probably the most parsimonious axiomatization based on , , , even proving the associativity laws (see box). He also proved that these axioms are independent of each other. In 1933, Huntington set out the following elegant axiomatization for Boolean algebra. It requires just one binary operation and a unary functional symbol , to be read as 'complement', which satisfy the following laws:

immediately asked: If the Huntington equation is replaced with its dual, to wit:

do (1), (2), and (4) form a basis for Boolean algebra? Calling (1), (2), and (4) a Robbins algebra, the question then becomes: Is every Robbins algebra a Boolean algebra? This question (which came to be known as the Robbins conjecture) remained open for decades, and became a favorite question of and his students. In 1996, at Argonne National Laboratory, building on earlier work by Larry Wos, Steve Winker, and Bob Veroff, answered Robbins's question in the affirmative: Every Robbins algebra is a Boolean algebra. Crucial to McCune's proof was the computer program EQP he designed. For a simplification of McCune's proof, see Dahn (1998).

Further work has been done for reducing the number of axioms; see Minimal axioms for Boolean algebra.

Generalizations
Removing the requirement of existence of a unit from the axioms of Boolean algebra yields "generalized Boolean algebras". Formally, a distributive lattice is a generalized Boolean lattice, if it has a smallest element and for any elements and in such that , there exists an element such that and . Defining as the unique such that and , we say that the structure is a generalized Boolean algebra, while is a generalized Boolean . Generalized Boolean lattices are exactly the ideals of Boolean lattices.

A structure that satisfies all axioms for Boolean algebras except the two distributivity axioms is called an orthocomplemented lattice. Orthocomplemented lattices arise naturally in as lattices of for .

See also
Notes
Works cited

General references
  • . See Section 2.5.
  • . See Chapter 2.
  • .

  • .
  • .
  • .
  • . In 3 volumes. (Vol.1:, Vol.2:, Vol.3:)
  • .
  • . Reprinted by Dover Publications, 1979.

External links

: ,
Page 1 of 1
1
Page 1 of 1
1

Account

Social:
Pages:  ..   .. 
Items:  .. 
Click to view the UPC Scavenger App on google play.

Navigation

General: Atom Feed Atom Feed  .. 
Help:  ..   .. 
Category:  ..   .. 
Media:  ..   .. 
Posts:  ..   ..   .. 

Statistics

Page:  .. 
Summary:  .. 
1 Tags
10/10 Page Rank
5 Page Refs